λ¬Έμ
Programmers - 거리λκΈ° νμΈνκΈ°
π Logic
private int bfs(int x, int y) {
Queue<Loc> queue = new LinkedList<>();
boolean[][] visited = new boolean[5][5];
int keep = 1;
visited[x][y] = true;
queue.add(new Loc(x, y, 0));
while(!queue.isEmpty()) {
Loc now = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = now.x + rangeX[i];
int ny = now.y + rangeY[i];
if (!isIn(nx, ny)) continue;
if (visited[nx][ny]) continue;
int nDist = now.dist + 1;
if (nDist > 2) continue;
char nP = place[nx].charAt(ny);
if (nP == 'P') return 0;
if (nP == 'X') continue;
visited[nx][ny] = true;
queue.add(new Loc(nx, ny, nDist));
}
}
return keep;
}
-
μμμμ μμΉλΆν° BFSλ₯Ό μμνλ€.
- λ€μ λ°©λ¬Έν μ§μ μ΄ μ΄λ―Έ λ°©λ¬Ένκ±°λ, λ²μλ₯Ό λ²μ΄λ κ²½μ°λ λ€μ μ§μ μ νμνκ³ ,
- κ±°λ¦¬κ° 2λ³΄λ€ ν° κ²½μ°λ λ μ΄μ νμΈνμ§ μμλ 거리λκΈ°κ° μ§μΌμ§ κ²½μ°μ΄λ―λ‘, λ€μ μ§μ μ νμνκ³ ,
- 2 μ΄νμ 거리μ λ€λ₯Έ μμμκ° μλ€λ©΄, 거리λκΈ°κ° μ§μΌμ§μ§ μμ κ²μΌλ‘, λ°λ‘ λ°ννλ€.
- λν νν°μ μ΄ μ‘΄μ¬νλ€λ©΄, λ μ΄μ νμΈνμ§ μμλ 거리λκΈ°κ° μ§μΌμ§ κ²½μ°μ΄λ―λ‘, λ€μ μ§μ μ νμνλ€.
- κ·Έλ μ§ μμ κ²½μ°μλ§ ν΄λΉ μ§μ μ λ°©λ¬Έ μ¬λΆλ₯Ό updateνκ³ νμ λ£λλ€. μ΄λ, 거리λ₯Ό 1μ© μ¦κ°νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Loc {
int x;
int y;
int dist;
public Loc(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
}
class WaitingRoom {
String[] place;
int[] rangeX = { 0, 1, 0, -1 };
int[] rangeY = { 1, 0, -1, 0 };
public WaitingRoom(String[] place) {
this.place = place;
}
public int checkKeepingDistance() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
char p = place[i].charAt(j);
if (p == 'P')
if (bfs(i, j) == 0)
return 0;
}
}
return 1;
}
private int bfs(int x, int y) {
Queue<Loc> queue = new LinkedList<>();
boolean[][] visited = new boolean[5][5];
int keep = 1;
visited[x][y] = true;
queue.add(new Loc(x, y, 0));
while(!queue.isEmpty()) {
Loc now = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = now.x + rangeX[i];
int ny = now.y + rangeY[i];
if (!isIn(nx, ny)) continue;
if (visited[nx][ny]) continue;
int nDist = now.dist + 1;
if (nDist > 2) continue;
char nP = place[nx].charAt(ny);
if (nP == 'P') return 0;
if (nP == 'X') continue;
visited[nx][ny] = true;
queue.add(new Loc(nx, ny, nDist));
}
}
return keep;
}
private boolean isIn(int x, int y) {
return (x < 5 && x >= 0 && y < 5 && y >= 0);
}
}
class Solution {
public int[] solution(String[][] places) {
int[] answer = new int[5];
int T = 0;
while (T < 5) {
WaitingRoom wr = new WaitingRoom(places[T]);
answer[T++] = wr.checkKeepingDistance();
}
return answer;
}
}
βοΈ Review
-
μ²μμλ DFS λ°©μμΌλ‘ ꡬννμΌλ, λͺλͺ ν μΌμμ νλ Έκ³ , λ¨μν νμ λ°©μμ μ°¨μ΄λκΉ BFSλ‘ κ΅¬νν΄λ λμΌν κ²μ΄λΌ μκ°νλ€.
- κ·Έλν νμ λ°©μμ λ¬Έμ κ° μλ, λ°ν κ°μ λ°ν 쑰건μ λν λ¬Έμ μλ€.
- λ€μ λ°©λ¬Έ μ§μ μ λν΄ λ§¨ν΄νΌ 거리λ₯Ό ꡬν΄λ³΄κ³ , 2 μ΄νμΈμ§ νμΈνλ λ°©μμμ νμ¬ μ§μ μμ λ€μ μ§μ μΌλ‘ μ΄λν λλ§λ€
distλ₯Ό 1μ© μ¦κ°μν€κ³ κ·Έ κ°μ ν¨κ» μ λ¬ν΄μ£Όλ λ°©μμΌλ‘ λ³κ²½νμ¬ μκ°μ μ€μΌ μ μμλ€.